#include<stdio.h>
#include<conio.h>
#include<stdlib.h>


//int line_search(int p[], int n, int x);
int binary_search(int p[], int n, int x);

int main()
{
    int n, i, *p, a, x;   
    printf ("How many elements do you want to input? - ");
    scanf ("%d", &n);
    p=malloc (n*sizeof(int));//initialize memory for array
    for (i=0; i<n; i++)//input each element
    {
        printf("Enter element no.%d: ",i+1);
        scanf("%d", p+i);
        }
    printf("Input the number you want to search: ");
    scanf("%d", &x);
    //a=line_search (p, n, x);
    a=binary_search(p, n, x);
    if(a>=0) printf("\nThe number that you search is at %d", a);
    else printf("\nCannot find it!!!");
    getch();
}

/*int line_search(int p[], int n, int x)
{
    int i=0;
    while (i<n)
              if (*(p+i)==x) return i;
                 else i++;
    return -1;
}*/

int binary_search(int p[], int n, int x)
{
    int i=0, mid;
    while (i<=n)
    {
          mid=(i+n)/2;
          if (*(p+mid)==x) return mid;
          else if (*(p+mid)>x) n=mid-1;
          else                 i=mid+1;
          }      
          return -1;
}
